package Leetcode;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class searchInsert {
    public int searchInsert(int[] nums, int target) {
        // 初始化左边界和右边界
        int left = 0, right = nums.length - 1;
        int mid = 0;

        // 使用二分查找缩小搜索范围
        while (left < right) {
            mid = (left + right) >>> 1;

            // 如果目标值大于中间值，说明插入位置在右边
            if (target > nums[mid]) {
                left = mid + 1;
            } 
            // 如果目标值小于中间值，说明插入位置在左边
            else if (target < nums[mid]) {
                right = mid - 1;
            } 
            // 找到目标值，直接返回索引
            else {
                return mid;
            }
        }

        // 循环结束时，left == right
        // 判断目标值是否大于当前元素，决定插入位置
        return target > nums[left] ? right + 1 : left;
    }
}
